Classifiers are used in many application environments, including machine learning, pattern recognition, and data mining. In general, a classifier provides a function that maps (or classifies) an instance into one of multiple predefined potential classes. A classifier typically predicts one attribute of a set of instances given one or more attributes (or features). The attribute being predicted typically is called the label, and the attributes used for prediction typically are called descriptive attributes. A classifier typically is constructed by an inducer, which is a method that builds the classifier from a training set of sample data. The training set consists of samples containing attributes, one of which is the class label. After a classifier has been built, its structure may be used to classify unlabeled instances as belonging to one or more of the potential classes.
Many different classifiers have been proposed. In application environments in which the amount of negative data is much greater than the amount of positive data, it has been discovered that it is computationally more efficient to decompose a complex single-stage classifier into a cascade of relatively simple classification stages. Such a cascaded classifier typically is designed so that the initial classification stages efficiently reject negative instances, and the final classification stages in the cascade only process the positive instances and the negative instances that are hard to distinguish from positive instances. In cases where the number of negative instances far outnumbers the number of positive instances, such a cascaded classifier is much more efficient than classifiers that process each instance in a single stage.
In a typical cascaded classifier design, each classification stage has a respective classification boundary that is controlled by a respective threshold. The overall classification boundary of the classifier is changed whenever one or more of the thresholds for the individual classification stages are changed. In a different cascaded classifier approach, each classification stage has two classification boundaries that are respectively controlled by an acceptance threshold and a rejection threshold. In one implementation, this approach is used to detect an object, such as a face in an image. Features in each image patch are evaluated through successive stages of the classifier to determine a cumulative score. At each stage, the image is rejected when the cumulative score is less than the rejection threshold and accepted when the cumulative score is greater than the acceptance threshold. The evaluating is repeated while the cumulative score is within a range of the acceptance threshold and the rejection threshold. In this approach, an image patch may be accepted at each of the classification stages. As a result, image patches may be accepted erroneously at unacceptably high rates unless the acceptance threshold is high, in which case a large number of classification stages would be needed to evaluate the image patches between the acceptance and rejection thresholds.
What is need is a classification approach in which marginal instances near the acceptance and rejection threshold boundaries are classified robustly and accurately without unduly increasing the number of the classification stages.